package DijkstraAlogorithm;

import java.util.Arrays;

public class DijkstraAlgorithm {
    public static void main(String[] args) {
        char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
        //邻接矩阵
        int[][] matrix = new int[vertex.length][vertex.length];
        final int N = 65535;// 表示不可以连接
        matrix[0]=new int[]{N,5,7,N,N,N,2};
        matrix[1]=new int[]{5,N,N,9,N,N,3};
        matrix[2]=new int[]{7,N,N,N,8,N,N};
        matrix[3]=new int[]{N,9,N,N,N,4,N};
        matrix[4]=new int[]{N,N,8,N,N,5,4};
        matrix[5]=new int[]{N,N,N,4,5,N,6};
        matrix[6]=new int[]{2,3,N,N,4,6,N};
        //创建 Graph对象
        Graph graph = new Graph(vertex, matrix);
        //测试, 看看图的邻接矩阵是否ok
        graph.showGraph();
        //测试迪杰斯特拉算法
        graph.dsj(2);//C
        graph.showDijkstra();
    }
}

class Graph {
    private char[] vertex; //节点数组
    private int[][] matrix;//邻接矩阵
    private VisiteVertex vv; //内含已经访问过的顶点集合

    public Graph(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
    }

    public void showGraph() {
        for (int[] link :
                matrix) {
            System.out.println(Arrays.toString(link));
        }
    }
    //迪杰斯特拉算法实现
    /**
     *
     * @param index 表示出发顶点对应的下标
     */
    public void dsj(int index) {
       //新建一个集合，用于记录访问过的节点的状态
        vv=new VisiteVertex(vertex.length,index);
        //用于更新index所指向的顶点到周围节点的距离
       update(index);
        for (int i = 1; i < vertex.length; i++) {
            index=vv.updateArr();//获取下一个要访问的节点坐标
            update(index);
        }
    }
    //更新index下标顶点到周围的距离和周围节点的前驱节点
    private void update(int index) {
        int len=0;
        //根据遍历我们的邻接矩阵,matrix[index]
        for (int i = 0; i < matrix[index].length; i++) {
          //len含义是 出发点到index的距离+从index顶点到i这个节点的距离
            len=vv.getDis(index)+matrix[index][i];
            //如果j的顶点没有访问过，体现在代码上就是dis[i] !=1
           //并且len所表示的距离比dis中的小,则更新dis[i]中的数值，代表找到更小的距离
            if(!vv.in(i)&&len<vv.getDis(i)){
                vv.updatePre(i,index);
                vv.updateDis(i,len);
            }
        }
    }
    //显示结果
    public void showDijkstra() {
        vv.show();
    }


}

class VisiteVertex {
    //记录各个顶点是否访问过，会随着程序的进行，动态更新。
    private int[] already_arr;
    //每个下标对应的值为前序节点，比如G为出发顶点
    private int[] pre_visited;
    //记录出发顶点到其他所有顶点
    public int[] dis;


    //构造器，初始化操作
    public VisiteVertex(int length, int index) {
        this.already_arr = new int[length];
        this.pre_visited = new int[length];
        this.dis = new int[length];
        //初始化dis
        Arrays.fill(dis, 65535);
        this.already_arr[index] = 1; //设置出发顶点被访问了
        this.dis[index] = 0; //设置出发点的访问距离为0
    }

    public int getDis(int index){
        return dis[index];
    }
    public boolean in(int index){
        return already_arr[index] == 1;
    }

    public void updatePre(int preIndex, int index) {
        pre_visited[preIndex]=index;
    }

    public void updateDis(int index, int len) {
        dis[index]=len;
    }

    /**
     * 继续选择并返回新的访问节点的坐标
     * @return
     */
    public int updateArr() {
        int min=65535,index=0;
        for (int i = 0; i < already_arr.length; i++) {
            if(already_arr[i]==0&&dis[i]<min){
                min=dis[i];
                index=i;
            }
        }
        //设置该节点为访问过的节点
        already_arr[index]=1;
        return index;
    }
    //显示最后的结果
    //即将三个数组的情况输出
    public void show() {

        System.out.println("==========================");
        //输出already_arr
        for(int i : already_arr) {
            System.out.print(i + " ");
        }
        System.out.println();
        //输出pre_visited
        for(int i : pre_visited) {
            System.out.print(i + " ");
        }
        System.out.println();
        //输出dis
        for(int i : dis) {
            System.out.print(i + " ");
        }
        System.out.println();
        //为了好看最后的最短距离，我们处理
        char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
        int count = 0;
        for (int i : dis) {
            if (i != 65535) {
                System.out.print(vertex[count] + "("+i+") ");
            } else {
                System.out.println("N ");
            }
            count++;
        }
        System.out.println();

    }
}
